package lab.chapter;

import java.util.*;

/**
 * 正则表达式相关
 */
public class Regex {

    public static void main(String[] args) {
        // first example
        //正则表达式：int|[a-zA-Z][a-zA-Z0-9]*|[0-9]+
        // testRegex(sampleGrammar1(), new String[] {"int", "intA", "23", "0A"});
        //
        // testRegex(sampleGrammar2(), new String[] {"abc", "abbcdcddbc", "abefs"});

        // simple grammar
        testRegex(sampleGrammar3(), new String[] {"int", "23"});

    }
    private static void testRegex(GrammarNode node, String[] testSet) {
        System.out.println("testing " + node.getName());
        System.out.println("node text  " + node.getText());
        node.dump();
        // nondeterministic finite automaton,不确定有限状态机
        System.out.println("\nNFA states:");
        State[] states = regexToNFA(node);
        states[0].dump();
        System.out.println("dump endState");
        states[1].dump();

        for (String s : testSet) {
            // 使用 NFA 匹配
            matchWithNFA(states[0], s);
        }

        System.out.println("\nNFA to DFA:");
        List<DFAState> dfaStateList = NFA2DFA(states[0], CharSet.letterAndDigits);
        dfaStateList.get(0).dump();
        for (String s : testSet) {
            // 使用 DFA 匹配
            matchWithDFA(dfaStateList.get(0), s);
        }
    }

    /**
     * 将正则表达式翻译成 NFA 不确定有限状态机
     * @param node 节点
     * @return NFA
     */
    public static State[] regexToNFA(GrammarNode node) {
        State beginState = null;
        State endState = null;

        switch (node.getType()) {
            // 转换成 s|t
            case Or:
                // 新的开始状态
                beginState = new State();
                // 新的接受状态
                endState = new State(true);
                for (GrammarNode child : node.children()) {
                    // 递归，生成子图，返回头尾两个状态
                    State[] childState = regexToNFA(child);
                    // 通过ε接到子图的开始状态
                    beginState.addTransition(new CharTransition(), childState[0]);
                    // 子图的结束状态，通过ε接到endState
                    childState[1].addTransition(new CharTransition(), endState);
                    childState[1].setAcceptable(false);
                }
                break;
            // 转换成 st
            case And:
                State[] lastChildState = null;
                for (int i = 0; i < node.getChildCount(); i++) {
                    // 生成子图
                    State[] childState = regexToNFA(node.getChild(i));
                    if (lastChildState != null) {
                        lastChildState[1].copyTransitions(childState[0]);
                        lastChildState[1].setAcceptable(false);
                    }
                    lastChildState = childState;
                    if (i == 0) {
                        // 整体开始状态
                        beginState = childState[0];
                    }  // 整体接受状态

                    endState = childState[1];
                }
                break;
            case Char:
                // 处理普通字符
                beginState = new State();
                endState = new State(true);
                // 图的边上是当前节点的charSet，也就是导致迁移的字符的集合，比如所有字母
                beginState.addTransition(new CharTransition(node.getCharSet()), endState);
                break;
        }
        State[] rtn;
        // 考虑重复的情况，增加必要的节点和边
        if (node.getMinTimes() != 1 || node.getMaxTimes() != 1) {
            rtn = addRepetition(beginState, endState, node);
        } else {
            rtn = new State[] {beginState, endState};
        }
        // 为命名语法节点做标记，用来设置 Token 类型
        if (node.getName() != null) {
            rtn[1].setGrammarNode(node);
        }

        return rtn;
    }

    /**
     * q将 NFA 转换成 DFA
     * @param startState 起始 NFA 状态
     * @param alphabet 该词法所采用的字符的集合
     * @return DFAState list
     */
    protected static List<DFAState> NFA2DFA(State startState, List<Character> alphabet) {
        List<DFAState> dfaStates = new LinkedList<>();
        List<DFAState> newStates = new LinkedList<>();

        Map<State, Set<State>> calculatedClosures = new HashMap<>();
        Set<State> stateSet = calcClosure(startState, calculatedClosures);
        DFAState dfaState = new DFAState(stateSet);
        dfaStates.add(dfaState);
        newStates.add(dfaState);

        // 每次循环都会计算出一些新的 StateSet 来。如果没有新的set，计算结束
        while (newStates.size() > 0) {
            List<DFAState> calculating = newStates;
            newStates = new LinkedList<>();
            for (DFAState dfaStateCalculated : calculating) {
                for (Character ch : alphabet) {
                    // 从状态集中接收字符 ch，能够迁移到的新状态的集合
                    Set<State> nextStateSet = move(dfaStateCalculated.states(), ch);
                    if (nextStateSet.size() == 0) {
                        continue;
                    }
                    calcClosure(nextStateSet, calculatedClosures);
                    // 看看是不是一个新的状态
                    dfaState = findDFAState(dfaStates, nextStateSet);
                    Transition transition = null;
                    if (dfaState == null) {
                        dfaState = new DFAState(nextStateSet);
                        dfaStates.add(dfaState);
                        newStates.add(dfaState);
                        transition = new CharTransition();
                        dfaStateCalculated.addTransition(transition, dfaState);
                    }
                    // 复用已有的迁移
                    if (transition == null) {
                        transition = dfaStateCalculated.getTransitionTo(dfaState);
                        if (transition == null) {
                            // 加上条件epsilon
                            transition = new CharTransition();
                            dfaStateCalculated.addTransition(transition, dfaState);
                        }
                    }
                    // 往 transition 添加字母
                    ((CharTransition) transition).condition.addSubSet(new CharSet(ch));
                }
            }
        }
        return dfaStates;
    }

    /**
     * 示例1： int | [a-zA-Z][a-zA-Z0-9]* | [0-9]*
     *
     * @return grammarNode
     */
    private static GrammarNode sampleGrammar1() {
        GrammarNode node = new GrammarNode("regex1", GrammarNodeType.Or);
        GrammarNode intNode = node.createChild(GrammarNodeType.And);
        // 关键字， int
        intNode.createChild(new CharSet('i'));
        intNode.createChild(new CharSet('n'));
        intNode.createChild(new CharSet('t'));
        // 标识符
        GrammarNode idNode = node.createChild(GrammarNodeType.And);
        idNode.createChild(CharSet.letter);
        GrammarNode letterOrDigit = idNode.createChild(CharSet.letterOrDigit);
        letterOrDigit.setRepeatTimes(0, -1);

        // 数字字面量
        GrammarNode literalNode = node.createChild(CharSet.digit);
        literalNode.setRepeatTimes(1, -1);
        return node;
    }

    /**
     * 示例 2， 正则表达式： a[a-zA-Z0-9]*bc
     * @return 语法节点
     */
    private static GrammarNode sampleGrammar2() {
        GrammarNode node = new GrammarNode("regex2", GrammarNodeType.And);
        node.createChild(new CharSet('a'));
        GrammarNode letterOrDigit = node.createChild(CharSet.letterOrDigit);
        letterOrDigit.setRepeatTimes(0, -1);
        node.createChild(new CharSet('b'));
        node.createChild(new CharSet('c'));
        return node;
    }

    private static State[] addRepetition(State state1, State state2, GrammarNode node) {
        State beginState;
        State endState;
        // 允许循环
        if (node.getMaxTimes() == -1 || node.getMaxTimes() > 1) {
            state2.addTransition(new CharTransition(node.getMaxTimes()), state1);
        }
        // 允许0次，此时需要加上2个节点
        if (node.getMinTimes() == 0) {
            beginState = new State();
            endState = new State(true);
            // epsilon to state1
            beginState.addTransition(new CharTransition(), state1);
            state2.addTransition(new CharTransition(), endState);
            state2.setAcceptable(false);
            // epsilon (skip) state1
            beginState.addTransition(new CharTransition(), endState);
        } else {
            beginState = state1;
            endState = state2;
        }
        return new State[] {beginState, endState};
    }

    /**
     * 看看字符是否符合 NFA
     * @param state NFA的起始状态
     * @param s 需要检查的字符
     * @return bool
     */
    private static boolean matchWithNFA(State state, String s) {
        System.out.println("NFA matching: '" + s + "'");
        char[] chars = s.toCharArray();
        int index = matchWithNFA(state, chars, 0);
        boolean match = index == chars.length;
        System.out.println("matched? : " + match + "\n");
        return match;
    }

    /**
     * NFA 匹配字符串
     * @param state 当前所在状态
     * @param chars 要匹配的字符串
     * @param index1 当前匹配字符开始的位置
     * @return 匹配后，新 index 的位置
     */
    private static int matchWithNFA(State state, char[] chars, int index1) {
        System.out.println("trying state: " + state.getName() + ", index =" + index1);
        int index2 = index1;
        for (Transition transition : state.transitions()) {
            State nextState = state.getState(transition);
            // epsilon 转换
            if (transition.isEpsilon()) {
                index2 = matchWithNFA(nextState, chars, index1);
                if (index2 == chars.length) {
                    // 本次匹配成功
                    break;
                }
                // 匹配失败，需要匹配另一条路径
            } else if (transition.match(chars[index1])) {
                // 消化一个字符，指针前移
                index2++;
                if (index2 < chars.length) {
                    index2 = matchWithNFA(nextState, chars, index1+1);
                } else {
                    // 已经扫描完所有字符
                    // 检查当前状态是否可接受，或者通过epsilon到达可接受状态
                    // 如果状态机还没到达接受状态，本次匹配失败
                    if (acceptable(nextState)) {
                        break;
                    } else {
                        index2 = -1;
                    }
                }
            }
        }
        return index2;
    }

    /**
     * 查找当前状态是否是一个接受状态，或者可以通过 epsilon 迁移到一个接受状态
     * @param state 当前状态
     * @return 是否可接受
     */
    private static boolean acceptable(State state) {
        if (state.isAcceptable()) {
            return true;
        }
        boolean rtn = false;
        for (Transition transition : state.transitions()) {
            if (transition.isEpsilon()) {
                State nextState = state.getState(transition);
                if (nextState.isAcceptable()) {
                    rtn = true;
                    break;
                } else {
                    rtn = acceptable(nextState);
                    if (rtn) {
                        break;
                    }
                }
            }
        }
        return rtn;
    }

    /**
     * 计算某个 state 通过 epsilon 能到达的所有 State
     * @param state 起始状态
     * @param calculatedClosures 已经计算的集合
     * @return 集合
     */
    private static Set<State> calcClosure(State state, Map<State, Set<State>> calculatedClosures) {
        if (calculatedClosures.containsKey(state)) {
            return calculatedClosures.get(state);
        }
        Set<State> closure = new HashSet<>();
        closure.add(state);
        for (Transition transition : state.transitions()) {
            if (transition.isEpsilon()) {
                State nextState = state.getState(transition);
                closure.add(nextState);
                closure.addAll(calcClosure(nextState, calculatedClosures));
            }
        }
        calculatedClosures.put(state, closure);
        return closure;
    }

    /**
     * 计算一个状态集合的闭包，包括这些状态以及可以通过 epsilon 到达的状态
     * @param states 待计算的集合
     * @param calculatedClosure 已经计算的集合
     */
    private static void calcClosure(Set<State> states, Map<State, Set<State>> calculatedClosure) {
        Set<State> newStates = new HashSet<>();
        for (State state : states) {
            Set<State> closure = calcClosure(state, calculatedClosure);
            newStates.addAll(closure);
        }
        states.addAll(newStates);
    }

    /**
     * 计算从某个状态集合，在接收某个字符以后，会迁移到哪些新的集合
     * @param states 待检查集合
     * @param ch 接收字符
     * @return 迁移的集合
     */
    private static Set<State> move(Set<State> states, Character ch) {
        Set<State> rtn = new HashSet<>();
        for (State state : states) {
            for (Transition transition : state.transitions()) {
                if (transition.match(ch)) {
                    State nextState = state.getState(transition);
                    rtn.add(nextState);
                }
            }
        }
        return rtn;
    }

    // 根据 NFA State 集合，查找是否已经存在一个 DFAState， 包含同样的NFA状态集合
    private static DFAState findDFAState(List<DFAState> dfaStates, Set<State> states) {
        DFAState dfaState = null;
        for (DFAState dfaState1 : dfaStates) {
            if (sameStateSet(dfaState1.states(), states)) {
                dfaState = dfaState1;
                break;
            }
        }
        return dfaState;
    }

    // 比较2个NFA 状态集是否相等
    private static boolean sameStateSet(Set<State> stateSet1, Set<State> stateSet2) {
        if (stateSet1.size() != stateSet2.size()) {
            return false;
        } else {
            return stateSet1.containsAll(stateSet2);
        }
    }

    private static boolean matchWithDFA(DFAState state, String s) {
        System.out.println("DFA matching: '" + s + "'");
        char[] chars = s.toCharArray();
        boolean match = matchWithDFA(state, chars, 0);
        System.out.println("matched? : " + match + "\n");
        return match;
    }

    /**
     * 基于 DFA 字符串匹配
     * @param state 匹配的状态
     * @param chars 待匹配的状态
     * @param index 匹配字符串中的索引
     * @return bool
     */
    private static boolean matchWithDFA(DFAState state, char[] chars, int index) {
        System.out.println("trying DFAState: " + state.getName() + ", index = " + index);
        // 根据字符，找到下一状态
        DFAState nextState = null;
        for (Transition transition : state.transitions()) {
            if (transition.match(chars[index])) {
                nextState = (DFAState) state.getState(transition);
                break;
            }
        }
        if (nextState != null) {
            if (index < chars.length -1) {
                // 继续匹配
                return matchWithDFA(nextState, chars, index + 1);
            } else {
                return nextState.isAcceptable();
            }
        } else {
            return false;
        }
    }

    /**
     * 示例1： int | [a-zA-Z]+
     *
     * @return grammarNode
     */
    private static GrammarNode sampleGrammar3() {
        GrammarNode node = new GrammarNode("regex3", GrammarNodeType.Or);
        // GrammarNode intNode = node.createChild(GrammarNodeType.And);
        // // 关键字， int
        // intNode.createChild(new CharSet('i'));
        // intNode.createChild(new CharSet('n'));
        // intNode.createChild(new CharSet('t'));
        // 字母
        GrammarNode letter = node.createChild(CharSet.letter);
        letter.setRepeatTimes(1, -1);

        return node;
    }

}
